<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <!-- 9. 使所有区间的异或结果为零
给你一个整数数组 nums 和一个整数 k 。区间 [left, right]（left <= right）的 异或结果 
是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。
  返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
  示例 1：
  输入：nums = [1,2,0,3,0], k = 1
  输出：3
  解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]
 -->
</head>
<body>
  <script>
    var minChanges = function(nums, k) {
    // x 的范围为 [0, 2^10)
    const MAXX = 2**10;

    const n = nums.length;
    let f = new Array(MAXX).fill(Number.MAX_VALUE);
    // 边界条件 f(-1,0)=0
    f[0] = 0;

    for (let i = 0; i < k; i++) {
        // 第 i 个组的哈希映射
        const count = new Map();
        let size = 0;
        for (let j = i; j < n; j += k) {
            count.has(nums[j]) ? count.set(nums[j], count.get(nums[j]) + 1) : count.set(nums[j], 1);
            size++;
        }

        // 求出 t2
        const t2min = Math.min(...f);

        const g = new Array(MAXX).fill(t2min);
        for (let mask = 0; mask < MAXX; mask++) {
            // t1 则需要枚举 x 才能求出
            for (const [x, countx] of count.entries()) {
                g[mask] = Math.min(g[mask], f[mask ^ x] - countx);
            }
        }

        // 别忘了加上 size
        for (const [index, val] of g.entries()) {
            f[index] = val + size;
        }
    }

    return f[0];
};
console.log(minChanges([1,2,0,3,0],1));
  </script>
</body>
</html>